// 将一些常见排序的代码放到了这里

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// 通用函数
void PrintArray(int* arr, int n);
void Swap(int* pn1, int* pn2);

// 冒泡排序 o(N^2)
void BubbleSort(int* arr, int n);
void TestBubbleSort(void);

// 插入排序 O(N^2)
void InsertSort(int* arr, int n);
void TestInsertSort(void);

// 堆排序 O(NlogN)
void AdjustDown(int* arr, int n, int parent);
void HeapSort(int* arr, int n);
void TestHeapSort(void);

// 希尔排序 O(N^1.3)
void ShellSort(int* arr, int n);
void TestShellSort(void);

// 选择排序 O(N^2)
void SelectSort(int* arr, int n);
void TestSelectSort(void);

// 快速排序 O(NlogN)
// 最坏情况下即有序时为O(N^2)
int GetMidi(const int* arr, int left, int right);
int Partition(int* arr, int left, int right);
void QuickSort(int* arr, int left, int right);
void TestQuickSort(void);

// 归并排序 O(NlogN)
void _MergeSort(int* arr, int left, int right, int* tmp);
void MergeSort(int* arr, int n);
void TestMergeSort(void);

// 计数排序 O(N + range)
void CountSort(int* arr, int n);
void TestCountSort(void);

// 给出大量随机数，比较排序所用时间
void TestOP(void);

int main(void)
{
//    TestInsertSort();
//    TestBubbleSort();
//    TestHeapSort();
//    TestShellSort();
//    TestSelectSort();
//    TestQuickSort();
//    TestMergeSort();
//    TestCountSort();
    TestOP();

    return 0;
}

void PrintArray(int* arr, int n)
{
    for (int i = 0 ; i < n ; i++){
        printf("%d ", arr[i]);
    }
    putchar('\n');
}

void Swap(int* pn1, int* pn2)
{
    int tmp = *pn1;
    *pn1 = *pn2;
    *pn2 = tmp;
}

void BubbleSort(int* arr, int n)
{
    // 非常不推荐，不优化的情况下都是O(N^2)
    for (int i = n ; i > 1 ; i--){
        // 加上小优化，没发生交换的情况下直接结束循环
        int exchange = 0;
        for (int j = 1 ; j < i ; j++){
            if (arr[j] < arr[j - 1]){
                exchange = 1;
                Swap(&arr[j], &arr[j - 1]);
            }
        }
        if (!exchange){
            break;
        }
    }
}

void TestBubbleSort(void)
{
    int arr[] = {5,2,6,9,8,1,3};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    BubbleSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void InsertSort(int* arr, int n)
{
    // 单趟到多趟的思想
    // 逆序的情况下最坏 O(N^2)
    // 正序的情况下最好 O(N)
    // [0,end]已经排好序，剩下end+1怎么排？
    for (int i = 0 ; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];

        while (end >= 0) {
            if (tmp < arr[end]) {
                arr[end + 1] = arr[end];
                end--;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

void TestInsertSort(void)
{
    int arr[] = {5,3,9,6,2,4,7,1,8};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    InsertSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void AdjustDown(int* arr, int n, int parent)
{
    // 假设法先选出大的孩子
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child] < arr[child + 1]){ // child + 1 < n是为了防止右孩子越界
            child += 1;
        }
        if (arr[child] > arr[parent]){
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapSort(int* arr, int n)
{
    // 要升序，建大堆
    for (int i = (n - 2) / 2 ; i >= 0 ; i--){
        AdjustDown(arr, n, i);
    }

    int end = n - 1;
    while (end > 0){
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        end--;
    }
}

void TestHeapSort(void)
{
    int arr[] = {5,3,6,7,4,2,3};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void ShellSort(int* arr, int n)
{
    // 预排序，接近有序
    // 直接插入排序，有序
    // 越大的数越快跳到后面，越小的数越快跳到前面
    int gap = n;
    while (gap > 1){
        gap /= 2;
        for (int i = 0 ; i < n - gap ; i++){ // 减少for循环的个数,每次对不同组进行预排序
            int end = i;
            int tmp = arr[end + gap];

            while (end >= 0){
                if (arr[end] > tmp){
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else {
                    break;
                }
                arr[end + gap]  = tmp;
            }
        }
    }
}

void TestShellSort(void)
{
    int arr[] = {5,6,9,8,3,2,5};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    ShellSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void SelectSort(int* arr, int n)
{
    int begin = 0, end = n - 1;

    while (begin < end) {
        int maxi = begin, mini = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (arr[i] > arr[maxi]) {
                maxi = i;
            }

            if (arr[i] < arr[mini]) {
                mini = i;
            }
        }

        // max与begin重叠,会发生错误
        Swap(&arr[begin], &arr[mini]);
        if (maxi == begin){ // 更新指针
            maxi = mini;
        }
        Swap(&arr[end], &arr[maxi]);

        begin++;
        end--;
    }
}

void TestSelectSort(void)
{
    int arr[] = {5,3,6,8,4,1};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    SelectSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

int GetMidi(const int* arr, int left, int right)
{
    // 三数取中 left mid right
    // 大小居中的值，不是最大也不是最小的
    int mid = (left + right) / 2;
    if (arr[left] < arr[mid]){
        if (arr[mid] < arr[right]){
            return mid;
        }
        else if (arr[left] > arr[right]){
            return left;
        }
        else {
            return right;
        }
    }
    else {
        if (arr[mid] > arr[right]){
            return mid;
        }
        else if (arr[left] < arr[right]){
            return left;
        }
        else {
            return right;
        }
    }
}

int Partition(int* arr, int left, int right)
{
    int prev = left, cur = left + 1;
    // 选择[left, right]区间中的随机数做key
    // 但选出来后还是与最左端数据交换
    // 不够理想，最理想是每次都选到中位数
//    int randi = rand() % (right - left + 1);
//    randi += left;
//    Swap(&arr[left], &arr[randi]);
    int midi = GetMidi(arr, left, right);
    Swap(&arr[left], &arr[midi]);
    int key = left;

    while (cur <= right){
        if (arr[cur] < arr[key] && ++prev != cur){
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }

    Swap(&arr[prev], &arr[key]);
    return prev;
}

void QuickSort(int* arr, int left, int right)
{
    // 选择了相对来说最完美的版本
    // 区间只有一个值或者不存在就是最小子问题
    // 意即前后指针法b
    if (left >= right){
        return ;
    }

    // 小区间优化，减少90％栈帧的消耗
    if (right - left + 1 < 10){
        InsertSort(arr + left, right - left + 1); // 注意这个left，不然会固定排前三个
    }

    else {
        int index = Partition(arr, left, right);

        QuickSort(arr, left, index - 1);
        QuickSort(arr, index + 1, right);
    }
}

void TestQuickSort(void)
{
    int arr[] = {5,3,7,5,9,3};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right){
        return ;
    }

    int mid = (left + right) >> 1;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);

    // 归并
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;

    while (begin1 <= end1 && begin2 <= end2){
        if (arr[begin1] < arr[begin2]){
            tmp[index++] = arr[begin1++];
        }
        else {
            tmp[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1){
        tmp[index++] = arr[begin1++];
    }

    while (begin2 <= end2){
        tmp[index++] = arr[begin2++];
    }

    // 拷贝回去，在回溯的过程中就要返回
//    for (int i = left ; i <= right ; i++){
//        arr[i] = tmp[i];
//    }
    memcpy(arr + left, tmp + left, sizeof(int)*(right - left + 1));
}

void MergeSort(int* arr, int n)
{
    int* tmp = (int*)malloc(sizeof(int)*n);

    _MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

void TestMergeSort(void)
{
    int arr[] = {1,5,6,8,2,6,5,3};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    MergeSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void CountSort(int* arr, int n)
{
    // 选出最大值，确定范围
    int max  = arr[0], min = arr[0];
    for (int i = 1 ; i < n ; i++){
        if (arr[i] > max){
            max = arr[i];
        }
        if (arr[i] < min){
            min = arr[i];
        }
    }
    int range = max - min + 1;

    int* count = (int*)malloc(sizeof(int)*range);

    if (count == NULL){
        printf("malloc fail\n");
        exit(-1);
    }
    memset(count, 0, sizeof(int) * range);

    for (int i = 0 ; i < n ; i++){
        count[arr[i] - min]++;
    }

    // 排序
    int j = 0;
    for (int i = 0 ; i < range ; i++){
        while (count[i]--){
            arr[j++] = i + min;
        }
    }
    free(count);
}

void TestCountSort(void)
{
    int arr[] = {5,2,3,6,9,8,5,4,2};

    PrintArray(arr, sizeof(arr) / sizeof(int));
    CountSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestOP(void)
{
    srand(time(0));
    const int N = 40000;

    int* arr1 = (int*)malloc(sizeof(int)*N);
    int* arr2 = (int*)malloc(sizeof(int)*N);
    int* arr3 = (int*)malloc(sizeof(int)*N);
    int* arr4 = (int*)malloc(sizeof(int)*N);
    int* arr5 = (int*)malloc(sizeof(int)*N);
    int* arr6 = (int*)malloc(sizeof(int)*N);
    int* arr7 = (int*)malloc(sizeof(int)*N);
    int* arr8 = (int*)malloc(sizeof(int)*N);

    for (int i = 0 ; i < N ; i++){
        arr1[i] = rand();
        arr2[i] = arr1[i];
        arr3[i] = arr2[i];
        arr4[i] = arr3[i];
        arr5[i] = arr4[i];
        arr6[i] = arr5[i];
        arr7[i] = arr6[i];
        arr8[i] = arr7[i];
    }

    int begin1 = clock();
    BubbleSort(arr1, N);
    int end1 = clock();

    int begin2 = clock();
    InsertSort(arr2, N);
    int end2 = clock();

    int begin3 = clock();
    ShellSort(arr3, N);
    int end3 = clock();

    int begin4 = clock();
    SelectSort(arr4, N);
    int end4 = clock();

    int begin5 = clock();
    HeapSort(arr5, N);
    int end5 = clock();

    int begin6 = clock();
    QuickSort(arr6, 0, N - 1);
    int end6 = clock();

    int begin7 = clock();
    MergeSort(arr7, N);
    int end7 = clock();

    int begin8 = clock();
    CountSort(arr8, N);
    int end8 = clock();

    printf("BubbleSort:%d\n", end1 - begin1);
    printf("InsertSort:%d\n", end2 - begin2);
    printf("ShellSort:%d\n", end3 - begin3);
    printf("SelectSort:%d\n", end4 - begin4);
    printf("HeapSort:%d\n", end5 - begin5);
    printf("QuickSort:%d\n", end6 - begin6);
    printf("MergeSort:%d\n", end7 - begin7);
    printf("CountSort:%d\n", end8 - begin8);

    free(arr1);
    free(arr2);
    free(arr3);
    free(arr4);
    free(arr5);
    free(arr6);
    free(arr7);
    free(arr8);
}


